#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from math import ceil

class Solution:
    """
    @param nums: A list of integers
    @return: An integer denotes the middle number of the nums
    """
    def median(self, nums):
        # write your code here
        assert nums
        self.nums = nums
        self.k = self.median_idx(nums)

        return self.quick_get_kth(0, len(nums))

    def median_idx(self, nums):
        l = len(nums)
        # if l == 1:
        #     return 0
        # else:
        #     return (l-1) // 2
        return (l-1) // 2

        # 这里用不到ceil: 是否所有的ceil都可以转为"//"符号运算?
        # return ceil(l/2) - 1

    def quick_get_kth(self, start, end):
        ''' [start, end)
            快排式查找kth element
        '''
        assert start <= (self.k) < end
        if end - start == 1:
            assert self.k == start
            return self.nums[start]

        self.shuffle_point(start, end)          # NOTE: 防止在排序数据上获得较差性能
        cmp_idx = start
        # print('start, end, self.k, cmp_idx (%s, %s, %s, %s)' % (start, end, self.k, cmp_idx))

        # range不包括end
        move_idx = start + 1
        for index in range(start+1, end):
            # 从start or start+1, 因为start是cmp_idx
            if self.nums[index] < self.nums[cmp_idx]:
                self.swap(index, move_idx)
                move_idx += 1
        self.swap(cmp_idx, move_idx-1)
        cmp_idx = move_idx-1

        # print(self.nums)
        # print(cmp_idx)

        if cmp_idx == self.k:
            return self.nums[cmp_idx]
        if cmp_idx < self.k:
            return self.quick_get_kth(cmp_idx + 1, end)
        if cmp_idx > self.k:
            return self.quick_get_kth(start, cmp_idx)        # 因为是开区间end), 所以cmp_idx不减1

    def shuffle_point(self, start, end):
        # [start, end)
        # 因为randint是闭区间, 所以需要end-1
        # 这里也可以选取中间数
        # choice_point = randint(start, end-1)
        choice_point = start + (end - start) // 2
        self.swap(start, choice_point)

    def swap(self, i1, i2):
        if i1 == i2: return
        l = self.nums
        l[i1], l[i2] = l[i2], l[i1]


def main():
    print("start main")

if __name__ == "__main__":
    main()
